package com.j4dream.property.leetcode.basic;

public class DynamicProgramming {
    // https://www.sohu.com/a/153858619_466939 概念参考。
    // 爬楼梯问题: 假设你正在爬楼梯。需要 n 步你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
    // 参考分析：
    // 假设十级，那么走完最后一步有两种方法， 第九级爬 1 台阶或第八级爬 2 台阶 依次递归。
    // 超时。。。
    public int climbStairs(int n) {
        if (n < 1) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    // 由于后面结果能依赖前面两次结果，可以迭代解决。
    public int climbStairs2(int n) {
        if (n < 1) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        int f = 1, s = 2, t = 0;
        for (int i = 3; i <= n; i++) {
            t = f + s;
            f = s;
            s = t;
        }
        return t;
    }

    // 国王金矿：有一个国家发现了5 (n) 座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10 (w) 人。每座金矿要么全挖，
    // 要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
    //
    public int getMostGold(int n, int w, int[] g, int[] p) {
        return 0;
    }

    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                profit = Math.max(prices[j] - prices[i], profit);
            }
        }
        return profit;
    }

    public int maxProfit2(int[] prices) {
        if (prices == null & prices.length == 0) return 0;
        int profit = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - min > profit) profit = prices[i] - min;
            if (prices[i] < min) min = prices[i];
        }
        return profit;
    }

    // 最大子序和
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int max = nums[0];
        int pre = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // pre + nums[i] > nums[i]
            if (pre > 0) {
                pre += nums[i];
            } else {
                pre = nums[i];
            }
            if (max < pre) {
                max = pre;
            }
        }
        return max;
    }

    //
    public int rob(int[] nums) {
        int curr = 0;
        int pre = 0;
        int t;
        for (int num : nums) {
            t = curr;
            curr = Math.max(curr, pre + num);
            pre = t;
        }
        return curr;
    }
}
